package com.datastructures2.graph.无向图;

/**
 * 判断G是否是无环图
 * @author MaoLin Wang
 * @date 2020/2/2117:31
 */
public class Cycle {
    private boolean[] marked;
    private boolean hasCycle;

    public Cycle(Graph G) {
        marked=new boolean[G.V()];
        for (int i = 0; i < G.V(); i++) {
            if (!marked[i]){
                dfs(G,i,i);
            }
        }
    }

    private void dfs(Graph G,int v, int u){
       marked[v]=true;
       for (int w:G.adj(v)){
           if (!marked[w]){
               dfs(G,w,v);;
           }else if (w!=u){
               hasCycle=true;
           }
       }
    }
    public boolean hasCycle(){
        return hasCycle;
    }

    public static void main(String[] args) {
        Graph graph=new Graph(7);
        graph.addEdge(0,1);
        graph.addEdge(0,2);
        graph.addEdge(0,3);
        graph.addEdge(1,4);
        graph.addEdge(6,1);
        graph.addEdge(4,5);
        graph.addEdge(6,2);
        Cycle cycle = new Cycle(graph);
        System.out.println(cycle.hasCycle());
    }
}
